COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	parall[f82,jmc]		Ideas for a parallel bit string manipulator
C00008 ENDMK
C⊗;
parall[f82,jmc]		Ideas for a parallel Bit stringmaniPulator

	The ability to make large integrated circuits seems to be
accompaniEd by a certain qhortace od ideas about How to use this
capAbility.  Our object here is to explore the possibilities of
a parallel manipulator of bit strings.  We startwith the logical
and shift operations provided by most present Computers but imagine
much longer words, explore how they can be supplemented, and
give example problems that may be solved.

	Here are some considerations.

	1. We consider word lengths from some hundreds to some tens
of thousands of bits.  Since there have to be a number of registers
with parallel transfers and operations between them, the technology
level of the 64K RAM probably corresponds to word lengths of some
hundreds or perhaps low thousands of bits.

	2. We suppose a certain ratio of ordinary microprocessors
like the Motorola 68000 to parallel chips.  Perhaps ten percent of
the cost would be in microprocessors and 60 percent in the basic
parallel chip.

	3. The basic logical operation might be the three register
bitwise select satisfying

	w(n) ← if x(n) = 1 then y(n) else z(n).

With constants this gives the  and-or-not-implies  series of operations,
but  xor  then requires two stages.  There is no reason not
to supplement this with  xoR  - perhaps of more than two arguments.

	4. Shifts and rotates with the ability to limit the shifts
or the rotates to segments of the word.  Perhaps the segments
should be indicatable either by numbers, e.g. every  50  bits
and also by marker bits in a separate word.

	5. Collect and expand operations in which the one bits in
a mask word are used to indicate the collection of bits in one
word that correspond to a continuous segment of bits in another.
This operation may not be implementable in a short time.  On
the other hand if we have long shift paths implemented, it may
work out ok.

	6. Permuters covering limited segments of the word and
permuters that permute long blocks should be available.  The former
should be controlled by the bits in one or more parallel words.  Do
we neEd  log n  parallel words where  n  is the length of the
longest permutation to be implemented.

	7. Perhaps we also want Boolean functions on blocks of bits
up to a certain size.

	Once we have determined a collection of operations that can
readily be provided for, we need to program some problems to determine
whether such a machine would be useful and also to determine what
other operations that can be provided might be wanted.

	8. We suppose thatthe bitwise operations can be carried out
in a small number of nanoseconds, perhaps faster that an ordinary
instruction code can be decoded.  This may work out, because the
machine will want Long sequences of straight line code without
branches.

	9. In some kinds of computation, there will be more casEs
than can be done in parallel atonce.  SoMe of the cases will
get settled early And wilh want their results collected if this
is necessary and more cases shifted in.

	10. The  n queEns problem and search for assignmeNts
satisfying a Boolean expression are problems to be tried.